In recent years, for example, in recent years, a key-value store method for managing data in key-and-value pairs has been known as a data storage method. FIG. 1 illustrates an example of a key-value store method. In the example in FIG. 1, records such as a record that includes key A and the value “hello” of the key A, and a record that includes key B and the value “world” of the key B are stored in a database. For example, when an inquiry (e.g. a get command “get (key=A)”) about key A is transmitted to the database, the value “hello” of the key A is returned from the database.
Furthermore, a distributed-type key-value store method is also known. FIG. 2 illustrates an example of a distributed processing system that uses a distributed-type key-value store method. In the example in FIG. 2, the distributed processing system includes node A to node D, and these nodes cooperate with each other to carry out a processing together. Also, in the example in FIG. 2, it is assumed that node A is in charge of the record for key A, node B is in charge of the record for key B and so on. For example, in the case of acquiring the value of the key A, an inquiry about the key A (i.e. a get command “get (key=A)”) is transmitted to one of the nodes. Here, it is assumed that an inquiry about the key A was transmitted to the node D. The node D receives the inquiry about the key A, searches for the node that is in charge of the key A, and transfers the inquiry to the node A, which is the node that is in charge of the key A. After receiving the inquiry about the key A, the node A reads out the value “hello” of the key A, from the database that the node A manages, and sends a response to the node D. Then, the node D receives the value “hello” of the key A from the node A and transmits that value to the user terminal. In this way, the user is able to obtain the desired value.
On the other hand, a method (for example, the Lamport algorithm) of expressing the order relationship of the processing between nodes using a logical clock in a distributed processing system is known. For example, as illustrated in FIG. 3, the node on the sender side sets the logical clock value at the time of transmission in a message as a time stamp and then transmits the message. The node on the receiver side calculates the new logical clock value by adding a predetermined value (“1” in FIG. 3) to the time stamp that was set in the message. Therefore, in the logical clock, time continues to advance, and time does not go backward (in other words, the logical clock value continues to advance, and that logical clock value is not reduced). In FIG. 3, a numerical value on the starting side of an arrow represents the logical clock value at a sender-side node, and a numerical value at the ending side of the arrow represents the logical clock value at a receiver-side node. In addition, the numerical value that is attached onto the arrow represents the time stamp that was set by the sender-side node (in other words, the logical clock value at the transmission time).
For example, in FIG. 3, when an event occurs at the node A and the logical clock value of the node A is 1, a message (a timestamp indicating 1) is transmitted from the node A to the node B. The logical clock value at the node B is 0 before reception of the message. After reception of the message, however, the node B determines that the logical clock value has increased to 1 since the timestamp included in the received message is 1 and thus uses, as a new logical clock value, a value (=2) obtained by adding 1 to the timestamp. Subsequently, when an event occurs at the node A and the logical clock value of the node A is 2, a message (a timestamp indicating 2) is transmitted from the node A to the node C. The logical clock value at the node C is 0 before reception of the message. After reception of the message, however, the node C determines that the logical clock value has increased to 2 since the timestamp included in the received message is 2 and thus uses, as a new logical clock value, a value (=3) obtained by adding 1 to the timestamp. Subsequently, when an event occurs at the node C and the logical clock value of the node C is 4, a message (a timestamp indicating 4) is transmitted from the node C to the node D. The logical clock value at the node D is 0 before reception of the message. After reception of the message, however, the node D determines that the logical clock value has increased to 4 since the timestamp included in the received message is 4 and thus uses, as a new logical clock value, a value (=5) obtained by adding 1 to the timestamp. When an event occurs at the node B and the logical clock value of the node B is 3, a message (a timestamp indicating 3) is transmitted from the node B to the node C. Although the timestamp included in the message received by the node C is 3, the logical clock value of the node C has increased to 4. Thus, the node C uses, as a new logical clock value, a value (=5) obtained by adding 1 to the logical clock value of the node C. Subsequently, when an event occurs at the node D and the logical clock value of the node D is 6, a message (a timestamp indicating 6) is transmitted from the node D to the node A. The logical clock value at the node A is 2 before reception of the message. After reception of the message, however, the node A determines that the logical clock value has increased to 6 since the timestamp included in the received message is 6 and thus uses, as a new logical clock value, a value (=7) obtained by adding 1 to the timestamp. Subsequently, when an event occurs at the node A and the logical clock value of the node A is 8, a message (a timestamp indicating 8) is transmitted from the node A to the node C. The logical clock value at the node C is 5 before reception of the message. After reception of the message, however, the node C determines that the logical clock value has increased to 8 since the timestamp included in the received message is 8 and thus uses, as a new logical clock value, a value (=9) obtained by adding 1 to the timestamp. When an event occurs at the node D and the logical clock value of the node D is 7, a message (a timestamp indicating 7) is transmitted from the node D to the node C. Although the timestamp included in the message received by the node C is 7, the logical clock value of the node C has increased to 9. Thus, the node C uses, as a new logical clock value, a value (=10) obtained by adding 1 to the logical clock value of the node C. As described above, each node performs the processing while changing the logical clock value.
Furthermore, some systems in distributed processing systems are applied eventual consistency as the data consistency model. Eventual Consistency is a consistency model that does not guarantee immediate consistency among all the replicas in a certain data store but does guarantee that they will all eventually reach the same value.
For example, FIG. 4 illustrates a distributed processing system in which eventual consistency has been applied. In the example in FIG. 4, it is assumed that the distributed processing system includes nodes A to G, and the node A is in charge of the record for key A. For example, in order to set a value for the key A, a user B operates the user terminal and inputs a set command “set (key=A, value=Y)”, after which the user terminal receives that input from the user B and sends the command to node F. Also, for example, in order to acquire the value of the key A, a user A operates the user terminal and inputs a get command “get (key=A)”, after which the user terminal receives the input from the user A and sends the get command to node C. Incidentally, for each command, at the instant that the command reaches a node, the node assigns a time stamp. In the example in FIG. 4, t=9 is assigned to the get command, and t=7 is assigned to the set command. In other words, in terms of the time stamp, the set command is older than the get command.
After that, as illustrated in FIG. 5, the node C searches for the node in charge of the key A, and transfers the get command to the node A, which is the node in charge of the key A. Similarly, the node F searches for the node in charge of the key A, and transfers the set command to the node A, which is the node in charge of the key A. Here, as illustrated in FIG. 5, it is assumed that a delay due to some reasons occur in the set command, so the get command arrives at the node A before the set command. In this case, as illustrated in FIG. 6, “X”, which was originally set, is acquired as the value of the key A. After that, when the set command arrives at the node A, the value of the key A is updated from “X” to “Y”. However, when the user A tries to acquire the value of the key A again after a certain period of time has elapsed, it is then possible to acquire the updated value “Y”. In this way, in a distributed processing system in which eventual consistency has been applied, as long as the newest value can finally be obtained, it is acceptable even if the newest value cannot be obtained a certain point in time.
However, as described above, from the point of view of eventual consistency, it is considered to be acceptable as long as the consistency in data eventually is obtained. Therefore, there was no viewpoint as to what point in time data consistency was obtained (or in other words, when data was “fixed”). Therefore, in distributed processing systems that have applied eventual consistency and a distributed-type key-value store method, it is impossible to identify how far data has been fixed at the present time in the overall system, and it is also impossible to know multiple data values (i.e. plural data values) at a certain period of time, while the logical clock value continues to advance.
In other words, in a distributed processing system managing a data value corresponding to each of plural keys, it is impossible to grasp the plural data values at a certain time point.